package LeetCode.month01.day27;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class No30 {
    public static void main(String[] args) {
        System.out.println(findSubstring("barfoothefoobarman", new String[]{"foo", "bar"}));
    }

    public static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        int wordlen = words[0].length();
        int windowlen = wordlen*words.length;
        HashMap<String,Integer> map = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            map.put(words[i],map.getOrDefault(words[i],0)+1);
        }

        for (int i = 0; i < wordlen; i++) {
            int overload = 0;
            HashMap<String,Integer> cnt = new HashMap<>();
            for (int j = i+wordlen; j <= s.length(); j+=wordlen) {
                String sub = s.substring(j-wordlen,j);
                if(cnt.getOrDefault(sub,0).equals(map.getOrDefault(sub,0))){
                    overload++;
                }
                cnt.put(sub,cnt.getOrDefault(sub,0)+1);
                int left = j-windowlen;
                if(left<0) continue;
                if(overload==0) res.add(left);
                String out = s.substring(left,left+wordlen);
                cnt.put(out,cnt.get(out)-1);
                if(cnt.get(out)==map.getOrDefault(out,0)) overload--;
            }
        }
        return res;
    }
//    public static List<Integer> findSubstring(String s, String[] words) {
//        List<String> list = new ArrayList<>();
//        dfs(list,0,words,new boolean[words.length],new StringBuilder());
//        List<Integer> res = new ArrayList<>();
//        int len = list.get(0).length();
//        StringBuilder sb = new StringBuilder(s.substring(0,len-1));
//        for (int i = len-1; i < s.length(); i++) {
//            sb.append(s.charAt(i));
//            if(list.contains(sb.toString())) res.add(i-len+1);
//            sb.deleteCharAt(0);
//        }
//        return res;
//    }
//
//    public static void dfs(List<String> list,int index,String[] words,boolean[] visit,StringBuilder sb){
//        if(index == words.length){
//            list.add(sb.toString());
//            return;
//        }
//        for (int i = 0; i < words.length; i++) {
//            if(!visit[i]){
//                sb.append(words[i]);
//                visit[i]=true;
//                dfs(list,index+1,words,visit,sb);
//                visit[i]=false;
//                sb.delete(sb.length()-words[i].length(),sb.length());
//            }
//        }
//    }
}
